import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static java.util.Arrays.asList;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 你可以按 任何顺序 返回答案。
 * leetcode 77 组合
 */
public class CombineNk {


    @Test
    public void test1() {
        List<List<Integer>> result = combine(4, 2);

        List<List<Integer>> correct = asList(asList(2, 4), asList(3, 4), asList(2, 3), asList(1, 2), asList(1, 3), asList(1, 4));
        Assertions.assertTrue(result.containsAll(correct));
        Assertions.assertTrue(correct.containsAll(result));


    }


    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        return combine(0, new ArrayList<>());
    }

    int n;
    int k;

    private List<List<Integer>> combine(int previousCount, List<Integer> previousResult) {
        if (previousCount > n) {
            return Collections.emptyList();
        }
        ArrayList<List<Integer>> result = new ArrayList<>();
        if (previousResult.size() == k) {

            result.add(previousResult);
            return result;
        }


        ArrayList<Integer> addCurrent = new ArrayList<>(previousResult);
        int current = previousCount + 1;
        addCurrent.add(current);
        List<List<Integer>> r1 = combine(current, addCurrent);
        List<List<Integer>> r2 = combine(current, previousResult);


        result.addAll(r1);
        result.addAll(r2);
        return result;
    }
}
